package com.mixsmart.commonweb.helper;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;

import com.mixsmart.commonweb.bean.BaseTree;
import com.mixsmart.commonweb.bean.IBaseTreeBean;
import com.mixsmart.utils.CollectionUtils;

/**
 * 树形结构帮助类 
 * <p>实现了BaseTree接口的Bean集合;</p>
 * 通过该类，可以得到树形结构的Bean集合
 * @author lmq
 * @version 1.0
 * @since JDK版本大于等于1.6
 * 2016年2月2日
 * @param <T>
 */
public class TreeHelper<T extends IBaseTreeBean> {
	
	private static final int HAS_CHILD = 1;
	private static final int NOT_CHILD = 0;
	
	/**
	 * 输出一个树形结构的列表
	 * @param ts 树形列表
	 * @param treeBean 树形对象
	 * @param isSelf 输出的集合中是否包含treeBean对象
	 * @return 返回处理后的树形列表
	 * @throws Exception
	 */
	public List<T> outPutTree(List<T> ts, T treeBean,boolean isSelf) throws Exception {
		List<T> trees = null; 
		if (null != ts && ts.size() > 0 && null != treeBean) {
			trees = new ArrayList<T>();
			//获取子树
			Stack<T> childStack = new Stack<T>();
			int count = 0;
			if(isSelf) {
				for (T tt : ts) {
					if (tt.getId().toString().equals(treeBean.getId().toString())) {
						treeBean = tt;
						count = 1;
						break;
					}
				}
			}
			childStack.push(treeBean);
			while (!childStack.isEmpty()) {
				T tt = childStack.pop();
				if (count>0) {
					trees.add(tt);
				}
				childStack.addAll(getChild(ts, tt));
				count++;
			}
		}
		return trees;
	}
	
	/**
	 * 输出一个树形结构的列表
	 * @param ts 树形列表
	 * @return 返回处理后的树形列表
	 * @throws Exception
	 */
	@SuppressWarnings("unchecked")
	public <E extends BaseTree<T>> List<E> outPutTree(List<T> ts) throws Exception {
		List<E> trees = null; 
		if (null != ts && ts.size() > 0) {
			trees = new ArrayList<E>();
			Set<T> sets = getRoot(ts);
			//set转换为list
			List<T> lists = new ArrayList<T>(sets);
			//list倒序
			Collections.reverse(lists);
			Stack<T> childStack = new Stack<T>();
			childStack.addAll(lists);
			while (!childStack.isEmpty()) {
				T treeBean = childStack.pop();
				List<T> childs = getChild(ts, treeBean);
				//判断是否存在
				E e = isExist(trees, treeBean);
				if(null == e) {
					e = (E) new BaseTree<T>();
					e.setTreeBean(treeBean);
					trees.add(e);
				}
				if(CollectionUtils.isNotEmpty(childs)) {
					e.setIsChild(HAS_CHILD);
					childStack.addAll(childs);
					addChilds(e, childs);
				} else {
					e.setIsChild(NOT_CHILD);
				}
			}
		}
		return trees;
	}
	
	/**
	 * 在父节点中添加子节点
	 * @param e 父节点
	 * @param ts 子节点集合
	 */
	@SuppressWarnings("unchecked")
	private <E extends BaseTree<T>> void addChilds(E e,List<T> ts) {
		List<E> childs = new ArrayList<E>();
		for (int i = ts.size()-1 ; i>=0 ; i--) {
			E child = (E) new BaseTree<T>();
			child.setTreeBean(ts.get(i));
			child.setIsChild(NOT_CHILD);
			childs.add(child);
		}
		e.setChilds(childs);
	}
	
	/**
	 * 判断父节点或子节点是否已经在列表中
	 * @param lists 树形列表
	 * @param treeBean 父节点或子节点对象
	 * @return 如果已经存在则返回节点对象；否则返回null
	 */
	@SuppressWarnings("unchecked")
	protected <E extends BaseTree<T>> E isExist(List<E> lists,T treeBean) {
		E beanTree = null;
		Stack<E> stacks = new Stack<E>();
		stacks.addAll(lists);
		while(!stacks.isEmpty()) {
			E e = stacks.pop();
			if(e.getTreeBean().getId().equals(treeBean.getId())) {
				beanTree = e;
				break;
			}  else if(CollectionUtils.isNotEmpty(e.getChilds())) {
				stacks.addAll((Collection<? extends E>) e.getChilds());
			}
		}
		return beanTree;
	}
	
	/**
	 * 获取根节点
	 * @param ts 树形
	 * @return 返回根节点集合
	 */
	protected TreeSet<T> getRoot(List<T> ts) {
		TreeSet<T> roots = null;
		if(null != ts && ts.size()>0) {
			roots = new TreeSet<T>(new Comparator<T>() {
				@Override
				public int compare(T o1, T o2) {
					int compare = o1.getSortNum().compareTo(o2.getSortNum());
					if(compare==0) {
						if(o1.getId().equals(o2.getId())) {
							compare = 0; 
						} else {
							compare = 1;
						}
					}
					return compare;
				}
			});
			for (T t : ts) {
				if(null == getParent(ts, t)) {
					roots.add(t);
				}
			}
		}
		return roots;
	}
	
	/**
	 * 获取父节点
	 * @param ts 树形集合
	 * @param treeBean 子节点对象
	 * @return 返回父节点
	 */
	protected T getParent(List<T> ts, T treeBean) {
		T tmp = null;
		for (T tt : ts) {
			if (tt.getId().toString().equals(treeBean.getParentId().toString())) {
				tmp = tt;
			}
		}
		return tmp;
	}
	
	/**
	 * 获取子节点
	 * @param ts 树形集合
	 * @param t 父节点
	 * @return 返回子节点列表
	 */
	protected List<T> getChild(List<T> ts, T t) {
		List<T> childs = new ArrayList<T>();
		for (T tt : ts) {
			if (tt.getParentId().toString().equals(t.getId().toString())) {
				// 此处保证集合中最后一个元素是需要显示在当前层级中第一个展示的子节点（因为堆栈中是最后一个元素先出）
				if (!childs.isEmpty() && (tt.getSortNum().intValue() >= childs.get(0).getSortNum().intValue())) {
					childs.add(0, tt);
				} else {
					childs.add(tt);
				}
			}
		}
		return childs;
	}
	
}
